// 2025/10/25
// N皇后二

class Solution {
public:
    int ans = 0;
    void dfs(vector<vector<int>>& board, int level)
    {
        int n = board.size();
        if(level == n)
        {
            ans++; return;
        }

        for(int i = 0; i < n; i++)
        {
            if(board[level][i] != 0)
                continue;
            
            for(int j = 1; j < n - level; j++)
            {
                board[level + j][i]++;
                if(i + j < n) board[level + j][i + j]++;
                if(i - j >= 0) board[level + j][i - j]++;
            }
            dfs(board, level + 1);
            for(int j = 1; j < n - level; j++)
            {
                board[level + j][i]--;
                if(i + j < n) board[level + j][i + j]--;
                if(i - j >= 0) board[level + j][i - j]--;
            }
        }
    }
    int totalNQueens(int n) {
        vector<vector<int>> board(n, vector<int>(n, 0));
        dfs(board, 0);
        return ans;
    }
};